public class MySqrt {
    public int mySqrt(int x){
        long left = 0;
        long right = x;
        long cur = 0;
        if(x < 1) return 0;

        while (left < right){
            long mid = left +(right - left + 1)/2;
            long mid2 = mid * mid;
            if (mid2 > x){
                right = mid - 1;
            }else if(mid2 < x){
                left = mid;
            }else {
                return (int)mid;
            }
            cur = left;
        }
        return (int)cur;
    }
}
